Fast Randomized Model Generation for Shapelet-Based Time Series Classification

摘要

Time series classification is a field which has drawn much attention over thepast decade. A new approach for classification of time series usesclassification trees based on shapelets. A shapelet is a subsequence extractedfrom one of the time series in the dataset. A disadvantage of this approach isthe time required for building the shapelet-based classification tree. Thesearch for the best shapelet requires examining all subsequences of all lengthsfrom all time series in the training set. A key goal of this work was to find an evaluation order of the shapeletsspace which enables fast convergence to an accurate model. The comparativeanalysis we conducted clearly indicates that a random evaluation order yieldsthe best results. Our empirical analysis of the distribution of high-qualityshapelets within the shapelets space provides insights into why randomizedshapelets sampling is superior to alternative evaluation orders. We present an algorithm for randomized model generation for shapelet-basedclassification that converges extremely quickly to a model with surprisinglyhigh accuracy after evaluating only an exceedingly small fraction of theshapelets space.